package lk;

import java.util.ArrayDeque;
import java.util.Deque;

public class D230924 {
    // 从字符串中移除星号
    public String removeStars(String s) {
        StringBuilder res = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (ch == '*') {
                res.deleteCharAt(res.length() - 1);
            } else {
                res.append(ch);
            }
        }
        return res.toString();
    }

    // 小行星碰撞
    public int[] asteroidCollision(int[] asteroids) {
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int n : asteroids) {
            boolean live = true;
            while (live && n < 0 && !stack.isEmpty() && stack.peek() > 0) {
                // 碰撞的条件：
                // 0. 当前小行星存活
                // 1. 当前小行星向左移动     n < 0
                // 2. 左边有小行星          !stack.isEmpty()
                // 3. 左边小行星向右移动     stack.peek() > 0
                live = -n > stack.peek() ? true : false;
                if (-n >= stack.peek()) {
                    stack.pop();
                }
            }
            if (live) {
                // 没有碰撞，或碰撞后小行星还存活，加入栈
                stack.push(n);
            }

        }
        int size = stack.size();
        int[] res = new int[size];
        for (int i = size - 1; i >= 0; i--) {
            res[i] = stack.pop();
        }
        return res;
    }
}
